package graphs;

import java.util.ArrayList;
import java.util.List;

/**
 * @param <T>
 * @file AMatrixGraph.java
 * @author Juan Humanes Ferrer
 * @date 04-Marzo-2014
 */
public class AMatrixGraph<T> implements GraphADT<T> {

    protected final int DEFAULT_CAPACITY = 10;
    protected int numVertices;   // number of vertices in the graph
    protected boolean[][] adjMatrix;   // adjacency matrix
    protected T[] vertices;   // values of vertices

    /**
     * Método que retorna el numero de vertices
     *
     * @return
     */
    @Override
    public int getNumVertices() {
        return numVertices;
    }

    /**
     * Método que modifica el numero de vertices
     *
     * @param numVertices
     */
    @Override
    public void setNumVertices(int numVertices) {
        this.numVertices = numVertices;
    }

    @Override
    public boolean[][] getAdjMatrix() {
        return adjMatrix;
    }

    public void setAdjMatrix(boolean[][] adjMatrix) {
        this.adjMatrix = adjMatrix;
    }

    /**
     * Clase dedicada a crear una matriz con la que se sabe el numero de
     * vertices y sus relaciones
     */
    public AMatrixGraph() {
        numVertices = 0;
        this.adjMatrix = new boolean[DEFAULT_CAPACITY][DEFAULT_CAPACITY];
        this.vertices = (T[]) (new Object[DEFAULT_CAPACITY]);
    }

    /**
     * ****************************************************************
     * Inserts an edge between two vertices of the graph.
     * **************************************************************** @param
     * index1
     * @param index2
     */
    @Override
    public void add2Edge(int index1, int index2) {
        if (indexIsValid(index1) && indexIsValid(index2)) {
            adjMatrix[index1][index2] = true;
            adjMatrix[index2][index1] = true;
        }
    }

    /**
     * ****************************************************************
     * Removes an edge between two vertices of the graph.
     * **************************************************************** @param
     * index1
     * @param index2
     */
    public void removeEdge(int index1, int index2) {
        if (indexIsValid(index1) && indexIsValid(index2)) {
            adjMatrix[index1][index2] = false;
            adjMatrix[index2][index1] = false;
        }
    }

    /**
     * ****************************************************************
     * Inserts an edge between two vertices of the graph.
     * **************************************************************** @param
     * vertex1
     */
    @Override
    public void addEdge(T vertex1, T vertex2) {
        add2Edge(getIndex(vertex1), getIndex(vertex2));
    }

    /**
     * ****************************************************************
     * Removes an edge between two vertices of the graph.
     * **************************************************************** @param
     * vertex1
     * @param vertex2
     */
    @Override
    public void removeEdge(T vertex1, T vertex2) {
        removeEdge(getIndex(vertex1), getIndex(vertex2));
    }

    /**
     * ****************************************************************
     * Adds a vertex to the graph, expanding the capacity of the graph if
     * necessary.
     * ****************************************************************
     */
    public void addVertex() {
        if (numVertices == vertices.length) {
            expandCapacity();
        }

        vertices[numVertices] = null;
        for (int i = 0; i <= numVertices; i++) {
            adjMatrix[numVertices][i] = false;
            adjMatrix[i][numVertices] = false;
        }
        numVertices++;
    }

    /**
     * ****************************************************************
     * Adds a vertex to the graph, expanding the capacity of the graph if
     * necessary. It also associates an object with the vertex.
     * **************************************************************** @param
     * vertex
     */
    @Override
    public void addVertex(T vertex) {
        if (numVertices == vertices.length) {
            expandCapacity();
        }

        vertices[numVertices] = vertex;
        for (int i = 0; i <= numVertices; i++) {
            adjMatrix[numVertices][i] = false;
            adjMatrix[i][numVertices] = false;
        }
        numVertices++;
    }

    /**
     * Metodo que determine si existe un vertice en el grafo
     *
     * @param gen
     * @return i : posicion del vertice en el grafo
     */
    @Override
    public int existeVertice(String gen) {
        boolean enc = false;
        int i = -1;

        while (enc == false && i < numVertices - 1) {
            i++;
            if (vertices[i].equals(gen)) {
                enc = true;
            }

        }

        if (enc == false) {
            i = -1;
        }
        return i;
    }

    /**
     * ****************************************************************
     * Removes a vertex at the given index from the graph. Note that this may
     * affect the index values of other vertices.
     * **************************************************************** @param
     * index
     */
    public void removeVertex(int index) {
        if (indexIsValid(index)) {
            numVertices--;

            for (int i = index; i < numVertices; i++) {
                vertices[i] = vertices[i + 1];
            }

            for (int i = index; i < numVertices; i++) {
                for (int j = 0; j <= numVertices; j++) {
                    adjMatrix[i][j] = adjMatrix[i + 1][j];
                }
            }

            for (int i = index; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    adjMatrix[j][i] = adjMatrix[j][i + 1];
                }
            }
        }
    }

    /**
     * ****************************************************************
     * Removes a single vertex with the given value from the graph.
     * **************************************************************** @param
     * vertex
     */
    @Override
    public void removeVertex(T vertex) {
        for (int i = 0; i < this.numVertices; i++) {
            if (vertex.equals(this.vertices[i])) {
                removeVertex(i);
                return;
            }
        }
    }

    /**
     * ****************************************************************
     * Creates new arrays to store the contents of the graph with twice the
     * capacity.
     * ****************************************************************
     */
    protected void expandCapacity() {
        T[] largerVertices = (T[]) (new Object[vertices.length * 2]);
        boolean[][] largerAdjMatrix
                = new boolean[vertices.length * 2][vertices.length * 2];

        for (int i = 0; i < numVertices; i++) {
            System.arraycopy(adjMatrix[i], 0, largerAdjMatrix[i], 0, numVertices);
            largerVertices[i] = vertices[i];
        }

        vertices = largerVertices;
        adjMatrix = largerAdjMatrix;
    }

    /**
     * ****************************************************************
     * Returns the number of vertices in the graph.
     * **************************************************************** @return
     */
    @Override
    public int size() {
        return numVertices;
    }

    /**
     * ****************************************************************
     * Returns true if the graph is empty and false otherwise.
     * **************************************************************** @return
     */
    @Override
    public boolean isEmpty() {
        return (numVertices == 0);
    }

    /**
     * ****************************************************************
     * Returns the index value of the first occurrence of the vertex. Returns -1
     * if the key is not found.
     * **************************************************************** @param
     * vertex
     * @return
     */
    public int getIndex(T vertex) {
        for (int i = 0; i < numVertices; i++) {
            if (vertices[i].equals(vertex)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * ****************************************************************
     * Returns true if the given index is valid.
     * **************************************************************** @param
     * index
     * @return
     */
    protected boolean indexIsValid(int index) {
        return ((index < numVertices) && (index >= 0));
    }

    /**
     * ****************************************************************
     * Returns a copy of the vertices array.
     * **************************************************************** @return
     */
    @Override
    public List<T> getVertices() {
        List<T> listaVertices = new ArrayList();
        T vertex;

        for (int i = 0; i < numVertices; i++) {
            vertex = this.vertices[i];
            listaVertices.add(vertex);
        }
        return listaVertices;
    }

    /**
     * Asigna el vector de vertices de entrada al del objeto
     *
     * @param vertices
     */
    @Override
    public void setVertices(T[] vertices) {
        this.vertices = vertices;

    }

    /**
     * Asigna la matriz de aristas de entrada al del objeto
     *
     * @param adjMatrix
     */
    @Override
    public void setAMtrix(boolean[][] adjMatrix) {
        this.adjMatrix = adjMatrix;

    }
}
